#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>

using namespace std;

class Solution
{
public:
    int ladderLength(string startGene, string endGene,
                     vector<string> &bank)
    {
        map<string, vector<string>> generalMap;
        for (auto &b : bank)
        {
            string s = b;
            for (int i = 0; i < b.size(); ++i)
            {
                char c = s[i];
                s[i] = '*';
                if (generalMap.find(s) == generalMap.end())
                    generalMap[s] = vector<string>();
                generalMap[s].push_back(b);
                s[i] = c;
            }
        }
        string s = startGene;
        for (int i = 0; i < startGene.size(); ++i)
        {
            char c = s[i];
            s[i] = '*';
            if (generalMap.find(s) == generalMap.end())
                generalMap[s] = vector<string>();
            generalMap[s].push_back(startGene);
            s[i] = c;
        }

        map<string, vector<string>> map;
        for (const string &b : bank)
        {
            map[b] = {};
            string s = b;
            for (int i = 0; i < b.size(); i++)
            {
                char c = s[i];
                s[i] = '*';
                if (generalMap.find(s) != generalMap.end())
                {
                    for (const string &a : generalMap[s])
                    {
                        map[b].push_back(a);
                    }
                }
                s[i] = c;
            }
        }
        s = startGene;
        map[startGene] = {};
        for (int i = 0; i < s.size(); i++)
        {
            char c = s[i];
            s[i] = '*';
            if (generalMap.find(s) != generalMap.end())
            {
                for (const string &a : generalMap[s])
                {
                    map[startGene].push_back(a);
                }
            }
            s[i] = c;
        }
        // search
        set<string> visited;
        queue<string> que;
        que.push(startGene);
        int level = 0;
        while (!que.empty())
        {
            int size = que.size();
            for (int i = 0; i < size; i++)
            {
                string cur = que.front();
                if (cur == endGene)
                    return level + 1;
                visited.insert(cur);
                for (auto c : map[cur])
                {
                    if (visited.find(c) == visited.end())
                    {
                        que.push(c);
                    }
                }
                que.pop();
            }
            level++;
        }
        return -1;
    }
};

int main()
{
    cout << "Code127" << endl;
    Solution s;
    cout << s.ladderLength("hit", "cog", vector<string>{"hot", "dot", "dog", "lot", "log", "cog"}) << endl;
}